#include "linklist.h"

namespace algorithm
{
        /**
     * @brief 第2题
     * 2 个逆序的链表，要求从低位开始相加，得出结果也逆序输出，返回值是逆序结果链表的头结点。
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 *一位* 的数字。
     * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
     * Output: 7 -> 0 -> 8
     * Explanation: 342 + 465 = 807.
     * 极端情况，例如
     * Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> )
     * Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1
     *
     * @param lst1 链表1
     * @param lst2 链表2
     * @return linkNode<int>* 返回的链表
     */
    linkNode<int> *AddTwoNums(linkNode<int> *lst1, linkNode<int> *lst2)
    {
        /**
         * @brief
         * 1.判断两个链表是否为空，若其中一个为空，则返回另一个；
         * 2.遍历两个链表，取当前节点的值，并更新节点到下个节点，当节点已经到末尾，则值为0；
         * 3.判断两个值相加是否有进位，有进位，则下一个节点的时还要加入进位的值；
         * 4.按头部插入节点的方法把计算的数据逐个加入链表；
         * 5.反转整个链表；
         */
        if (lst1 == nullptr)
            return lst2;
        if (lst2 == nullptr)
            return lst1;

        linkNode<int> *tmp1 = lst1, *tmp2 = lst2, *lst = nullptr;
        int carry = 0;
        while (tmp1 != nullptr || tmp2 != nullptr)
        {
            int val1, val2;
            if (tmp1 == nullptr)
                val1 = 0;
            else
            {
                val1 = tmp1->val;
                tmp1 = tmp1->next;
            }

            if (tmp2 == nullptr)
                val2 = 0;
            else
            {
                val2 = tmp2->val;
                tmp2 = tmp2->next;
            }
            // 产生一个节点，并加入到待返回的链表中
            int val = (val1 + val2 + carry) % 10;
            linkNode<int> *node = new linkNode<int>(val);
            if (lst == nullptr)
                lst = node;
            else
            {
                linkNode<int> *tmp = lst;
                lst = node;
                lst->next = tmp;
            }

            if ((val1 + val2 + carry) < 10)
                carry = 0;
            else
                carry = 1;
        }
        //检测最后一个节点是否有进位，如果有进位，则需要加入进位节点
        if (carry != 0)
        {
            linkNode<int> *node = new linkNode<int>(carry);
            linkNode<int> *tmp = lst;
            lst = node;
            lst->next = tmp;
        }

        linkNode<int> *begin = lst, *end = lst->next;
        while (end != nullptr)
        {
            begin->next = end->next;
            end->next = lst;
            lst = end;
            end = begin->next;
        }
        return lst;
    }

}